package LeetCode;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LC_648_ReplaceWords {

    public static void main(String[] args) {

    }

    public class Solution {
        public String replaceWords(List<String> dict, String sentence) {
            Set<String> set = new HashSet<>();
            set.addAll(dict);
            String Words[] = sentence.split(" ");
            StringBuilder replaceWords = new StringBuilder();
            for (int i = 0; i < Words.length; i++)
                for (int j = 0; j < Words[i].length(); j++)
                    if (set.contains(Words[i].substring(0, j + 1))) {
                        Words[i] = Words[i].substring(0, j + 1);
                        break;
                    }
            for (String Word : Words) replaceWords.append(Word).append(" ");
            return replaceWords.substring(0, replaceWords.length() - 1);
        }
    }

}